from typing import List

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True

        leftResult, rightResult = [], []
        self.leftFirst(root.left, 0, leftResult)
        self.rightFirst(root.right, 0, rightResult)
        return leftResult == rightResult

    def leftFirst(self, node: TreeNode, h: int, result):
        if node == None:
            return

        self.leftFirst(node.left, h + 1, result)
        result.append((node.val, h))
        self.leftFirst(node.right, h + 1, result)

    def rightFirst(self, node: TreeNode, h: int, result):
        if node == None:
            return

        self.rightFirst(node.right, h + 1, result)
        result.append((node.val, h))
        self.rightFirst(node.left, h + 1, result)